Codeforces Round #110 (Div. 2)

A

弱智题,统计一下每行每列的和即可。

时间复杂度 O(n2)O(n^2)

Code

#include <cstdio>

const int N = 35;

int a[N][N], row[N], col[N], n, res;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            row[i] += a[i][j];
            col[j] += a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (col[j] > row[i]) res++;
    }
    printf("%d\n", res);
}

B

对半径从大到小排序,顺次模拟即可。

时间复杂度 O(nlogn)O(n\log{n})

Code

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5;
const double pi = acos(-1);

double r[N], res;

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf", &r[i]);
    sort(r + 1, r + n + 1);
    reverse(r + 1, r + n + 1);
    for (int i = 1; i <= n; i++) {
        if (i & 1) res += pi * r[i] * r[i];
        else res -= pi * r[i] * r[i];
    }
    printf("%.10lf\n", res);
}

C

由于插入和删除都是在头尾进行的,可以枚举 bb 的左端点在 aa 中的位置,暴力匹配即可。

时间复杂度 O(nm)O(nm)

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2005;

char a[N], b[N];

int main() {
    scanf("%s%s", a + 1, b + 1);
    int n = strlen(a + 1);
    int m = strlen(b + 1);
    int ans = m;
    for (int i = -m; i <= n; i++) {
        int res = m;
        for (int j = 1; j <= m; j++) {
            if (i + j <= 0 || i + j >= n + 1) continue;
            if (a[i + j] == b[j]) res--;
        }
        ans = min(ans, res);
    }
    printf("%d\n", ans);
}

D

有趣的推理题。

对于每一个人,设 TiT_i 为指控这个人是罪犯的人数,FiF_i 为指控这个人不是罪犯的人数。

先假设所有人都不是罪犯,处理出来 TiT_iFiF_i 的值,同时记录 nn 句话中真话数量 ss

然后我们让每个人尝试成为罪犯。如果 ii 成为罪犯,那么 TiT_iFiF_i 将会互换。原本 ss 句真话中有 FiF_i 句会变为假话,TiT_i 句变为真话。

而一共有 mm 句真话,所以当且仅当
s+TiFi=ms + T_i - F_i = mii 才有可能成为罪犯。我们记录下来可能成为罪犯的人以及可能成为罪犯的人数。

然后就可以输出了。对于第 ii 句话,判断一下这句话指控的人是否可能为罪犯以及罪犯人数即可。

时间复杂度 O(n)O(n)

Code

#include <cstdio>

const int N = 1e5 + 5;

int n, m, s, cnt, a[N], sus[N], con[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (a[i] > 0) con[a[i]]++;
        else con[-a[i]]--, s++;
    }
    for (int i = 1; i <= n; i++)
        if (con[i] + s == m) {
            cnt++;
            sus[i] = 1;
        }
    for (int i = 1; i <= n; i++) {
        if (a[i] > 0) {
            if (!sus[a[i]]) puts("Lie");
            else if (cnt == 1) puts("Truth");
            else puts("Not defined");
        } else {
            if (!sus[-a[i]]) puts("Truth");
            else if (cnt == 1) puts("Lie");
            else puts("Not defined");
        }
    }
}

E

我们将字符 a\texttt{a}z\texttt{z} 对应为 112626 ,容易发现每一次操作整个串的和是不变的。

由于操作可以传递,变换相邻字符的操作可以经过若干次操作变成变换任意两个字符。于是问题就变成了给定总和求字符串个数。

很显然的dp。设 fi,jf_{i,\,j} 为字符串 ss 的前 ii 位和为 jj 的总数。转移方程显然

fi,j=k=1min{j,26}fi1,jkf_{i,\,j}=\sum\limits_{k=1}^{\min\{j,26\}}f_{i-1,\,j-k}

由于多组数据,我们可以先预处理 fi,jf_{i,\,j} ,询问直接输出即可。

时间复杂度 O(262n2)O(26^2n^2)

Code

#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 105;
const int mod = 1e9 + 7;

int f[N][N * 26], n, sum, T;
char s[N];

int main() {
    f[0][0] = 1;
    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= 2600; j++)
            for (int k = 1; k <= min(j, 26); k++)
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
    }
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s);
        sum = 0;
        n = strlen(s);
        for (int i = 0; i < n; i++) sum += s[i] - 'a' + 1;
        printf("%d\n", f[n][sum] - 1);
    }
}
赞赏